package suanfa.linklist;

public class KthFromEnd {


    public static Node findKthFromEnd(Node head,int k){
        Node p1=head;
        Node p2=head;
//i=0,自己一开始写的0，找倒数第3个元素，但是找到的是倒数第4个元素
        for (int i = 1; i < k; i++) {
            p2=p2.next;

            if(p2==null){
                throw new IllegalArgumentException("参数n超出链表长度");
            }
        }

        while(p2.next!=null){
            p1=p1.next;
            p2=p2.next;
        }

        return p1;
    }


    private static Node buildlLinkedList(int[] array){
        Node head=new Node(array[0]);

        Node p=head;
//i=0,自己一开始写的0，找倒数第3个元素，但是找到的是倒数第4个元素
        for (int i = 1; i < array.length; i++) {
            p.next=new Node(array[i]);

            p=p.next;
        }

        return head;
    }

    private static class Node{
        int data;
        Node next;

        Node(int data){
            this.data=data;
        }
    }

    public static void main(String[] args) {
        //1,2,3,4,5,7,8,9
        int[] inputs={5,3,7,2,4,9,1,8};

        Node head=buildlLinkedList(inputs);

        Node node=findKthFromEnd(head,3);

        System.out.println("链表倒数第三个元素是："+node.data);

    }
}
